package main

import "fmt"

func main() {

	node1 := &Node{Value: 1}
	node2 := &Node{Value: 2}
	node3 := &Node{Value: 3}
	node4 := &Node{Value: 4}
	node5 := &Node{Value: 5}
	node6 := &Node{Value: 6}
	node7 := &Node{Value: 7}
	node8 := &Node{Value: 8}

	node1.Left = node2
	node1.Right = node3
	node2.Left = node4
	node2.Right = node5
	node3.Left = node6
	node3.Right = node7

	hh := nearAnc(node1, node2, node8)
	fmt.Println(hh)

}

type Node struct {
	Value int
	Left  *Node
	Right *Node
}

func nearAnc(root, p, q *Node) *Node {
	if root == nil || root == p || root == q {
		return root
	}
	left := nearAnc(root.Left, p, q)
	right := nearAnc(root.Right, p, q)

	if left != nil && right != nil {
		return root
	}

	if left != nil && right == nil {
		return left
	}

	if right != nil && left == nil {
		return right
	}

	return nil
}
